#include <iostream>
#include <fstream>

template <bool f, int a, int b>
struct Compare{};

template <int a, int b>
struct Compare <false, a, b>
{
	static const int res = b;
};

template <int a, int b>
struct Compare <true, a, b>
{
	static const int res = a;
};

struct empty_list {};

template <int value, typename T>
struct List
{
	static const int Head = value;
	typedef T Tail;
};

template <int a, typename T, bool reverse>
struct push
{
	static const int minimum = Compare <(reverse ^ (a < T::Head)), a, T::Head> ::res;
	static const int maximum = Compare <(reverse ^ (a > T::Head)), a, T::Head> ::res;
	typedef List
	<
		minimum, 
		typename push
		<
			maximum, 
			typename T::Tail,
			reverse
		> ::list
	> list;
};

template <int a, bool reverse>
struct push <a, empty_list, reverse>
{
	typedef List <a, empty_list> list;
};

template <typename T, bool reverse>
struct sort
{
	typedef typename push
	<
		T::Head,
		typename sort
		<
			typename T::Tail,
			reverse
		>::list,
		reverse
	>::list list;
};

template <bool reverse>
struct sort <empty_list, reverse>
{
	typedef empty_list list;
};

template <int a, typename T>
std::ostream& operator << (std::ostream& output, List <a, T> List_)
{
	return output << List_.Head << " " << T();
};

std::ostream& operator << (std::ostream& output, empty_list List_)
{
	return output;
};

int main()
{
	typedef List <2116, List <42, List<23, List<239, List<-17, List<23, empty_list> > > > > > List_;
	std::cout << sort<List_, false>::list() << std::endl;
	std::cout << sort<List_, true>::list() << std::endl;
	return 0;
}


